import java.util.Arrays;

public class sort {
    public static void Sort(int[] a) {
        for(int i=1;i<a.length;i++) {
            int current=a[i];
            int n=i-1;
            while(n>=0 && a[n]>current) {
                a[n+1]=a[n];
                n--;
            }
            a[n+1]=current;
        }
    }

    public static void main(String[] args) {
        int arr[]={3,5,4,8,5,8,9};
        Sort(arr);
        System.out.println(Arrays.toString(arr));

    }
}
